package org.example.myleet.p427;

public class Solution {
    public Node construct(int[][] grid) {
        int n = grid.length;
        Node root = new Node();
        dfs(grid, n >>> 1, 0, 0, root);
        return root;
    }

    private void dfs(int[][] grid, int n, int r, int c, Node parent) {
        if (n == 0) {
            //没有更细粒度的递归，直接作为叶子节点
            parent.isLeaf = true;
            parent.val = grid[r][c] != 0;
            parent.topLeft = null;
            parent.topRight = null;
            parent.bottomLeft = null;
            parent.bottomRight = null;
            return;
        }
        int score = 0;
        //top left
        Node topLeft = new Node();
        dfs(grid, n >>> 1, r, c, topLeft);
        if (topLeft.val) {
            ++score;
        }
        parent.topLeft = topLeft;
        //top right
        Node topRight = new Node();
        dfs(grid, n >>> 1, r, c + n, topRight);
        if (topRight.val) {
            ++score;
        }
        parent.topRight = topRight;
        //bottom left
        Node bottomLeft = new Node();
        dfs(grid, n >>> 1, r + n, c, bottomLeft);
        if (bottomLeft.val) {
            ++score;
        }
        parent.bottomLeft = bottomLeft;
        //bottom right
        Node bottomRight = new Node();
        dfs(grid, n >>> 1, r + n, c + n, bottomRight);
        if (bottomRight.val) {
            ++score;
        }
        parent.bottomRight = bottomRight;
        //通过score决定分数
        if (score == 0) {
            parent.val = false;
        } else if (score == 4) {
            parent.val = true;
        } else {
            //0、1为false，2、3为true
            parent.val = score >= 2;
        }
        if (score == 0 || score == 4) {
            //四个子网格全相等的情况下，当四个子网格全为叶子节点时，parent网格也应成为叶子节点
            if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf) {
                parent.isLeaf = true;
                parent.topLeft = null;
                parent.topRight = null;
                parent.bottomLeft = null;
                parent.bottomRight = null;
            } else {
                parent.isLeaf = false;
            }
        } else {
            parent.isLeaf = false;
        }
    }
}
